#include <stdio.h>
#include <stdlib.h>
#define INFINITY 999999
typedef struct 
{
    int weight;
    int parent, lchild, rchild;
} HNODE;
typedef HNODE* HuffmanTree;
void SelectMinTwo(HuffmanTree ht, int n, int *s1, int *s2) 
{
    int i, x1, x2, w1, w2;
    w1 = w2 = INFINITY;
    x1 = x2 = 0;
    for (i = 1; i <= n; i++) 
	{
        if (ht[i].parent == 0) 
		{
            if (ht[i].weight < w1) 
			{
                w2 = w1, x2 = x1;
                w1 = ht[i].weight;
                x1 = i;
            } 
			else if (ht[i].weight < w2) 
			{
                w2 = ht[i].weight;
                x2 = i;
            }
        }
    }
    if (x1) *s1 = x1;
    if (x2) *s2 = x2;
}

HuffmanTree CreateHuffmanTree(int n, int *weights) 
{
    int i, s1, s2;
    HuffmanTree ht;
    if (n < 2) return NULL;
    ht = (HuffmanTree)malloc(sizeof(HNODE) * (2 * n));
    for (i = 1; i <= 2 * n - 1; i++)
        ht[i].parent = ht[i].lchild = ht[i].rchild = 0;
    for (i = 1; i <= n; i++) 
	{
        ht[i].weight = weights[i-1];
    }
    for (i = n + 1; i <= 2 * n - 1; i++) 
	{
        SelectMinTwo(ht, i - 1, &s1, &s2);
        ht[s1].parent = ht[s2].parent = i;
        ht[i].lchild = s1, ht[i].rchild = s2;
        ht[i].weight = ht[s1].weight + ht[s2].weight;
    }
    return ht;
}

int WPL(HuffmanTree ht, int n) 
{
    int wpl = 0;
    for (int i = 1; i <= n; i++) 
	{
        int depth = 0;
        int j = i;
        while (ht[j].parent != 0) 
		{
            depth++;
            j = ht[j].parent;
        }
        wpl += ht[i].weight * depth;
    }
    return wpl;
}

int main() 
{
    int t;
    scanf("%d", &t);
    while (t--) 
	{
        int n;
        scanf("%d", &n);
        int *weights = (int*)malloc(n * sizeof(int));
        for (int i = 0; i < n; i++) 
		{
            scanf("%d", &weights[i]);
        }
        HuffmanTree ht = CreateHuffmanTree(n, weights);
        int wpl = WPL(ht, n);
        printf("%d\n", wpl);
        free(ht);
        free(weights);
    }
    return 0;
}
